home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / • Extras • / SGI STL / heap.h < prev    next >
C/C++ Source or Header  |  1997-05-28  |  8KB  |  221 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. /*
  17.  *
  18.  * Copyright (c) 1997
  19.  * Moscow Center for SPARC Technology
  20.  *
  21.  * Permission to use, copy, modify, distribute and sell this software
  22.  * and its documentation for any purpose is hereby granted without fee,
  23.  * provided that the above copyright notice appear in all copies and
  24.  * that both that copyright notice and this permission notice appear
  25.  * in supporting documentation.  Moscow Center for SPARC Technology makes no
  26.  * representations about the suitability of this software for any
  27.  * purpose.  It is provided "as is" without express or implied warranty.
  28.  *
  29.  */
  30.  
  31.  
  32. #ifndef __SGI_STL_HEAP_H
  33. #define __SGI_STL_HEAP_H
  34.  
  35. # ifndef __SGI_STL_BOOL_H
  36. #  include <bool.h>
  37. # endif
  38.  
  39. __BEGIN_STL_NAMESPACE
  40.  
  41. template <class RandomAccessIterator, class Distance, class T>
  42. void __push_heap(RandomAccessIterator first, Distance holeIndex,
  43.          Distance topIndex, T value) {
  44.     Distance parent = (holeIndex - 1) / 2;
  45.     while (holeIndex > topIndex && *(first + parent) < value) {
  46.     *(first + holeIndex) = *(first + parent);
  47.     holeIndex = parent;
  48.     parent = (holeIndex - 1) / 2;
  49.     }    
  50.     *(first + holeIndex) = value;
  51. }
  52.  
  53. template <class RandomAccessIterator, class Distance, class T>
  54. inline void __push_heap_aux(RandomAccessIterator first,
  55.                 RandomAccessIterator last, Distance*, T*) {
  56.     __push_heap(first, Distance((last - first) - 1), Distance(0), 
  57.         T(*(last - 1)));
  58. }
  59.  
  60. template <class RandomAccessIterator>
  61. inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  62.     __push_heap_aux(first, last, distance_type(first), value_type(first));
  63. }
  64.  
  65. template <class RandomAccessIterator, class Distance, class T, class Compare>
  66. void __push_heap(RandomAccessIterator first, Distance holeIndex,
  67.          Distance topIndex, T value, Compare comp) {
  68.     Distance parent = (holeIndex - 1) / 2;
  69.     while (holeIndex > topIndex && comp(*(first + parent), value)) {
  70.     *(first + holeIndex) = *(first + parent);
  71.     holeIndex = parent;
  72.     parent = (holeIndex - 1) / 2;
  73.     }
  74.     *(first + holeIndex) = value;
  75. }
  76.  
  77. template <class RandomAccessIterator, class Compare, class Distance, class T>
  78. inline void __push_heap_aux(RandomAccessIterator first,
  79.                 RandomAccessIterator last, Compare comp,
  80.                 Distance*, T*) {
  81.     __push_heap(first, Distance((last - first) - 1), Distance(0), 
  82.         T(*(last - 1)), comp);
  83. }
  84.  
  85. template <class RandomAccessIterator, class Compare>
  86. inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
  87.               Compare comp) {
  88.     __push_heap_aux(first, last, comp, distance_type(first), value_type(first));
  89. }
  90.  
  91. template <class RandomAccessIterator, class Distance, class T>
  92. void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
  93.            Distance len, T value) {
  94.     Distance topIndex = holeIndex;
  95.     Distance secondChild = 2 * holeIndex + 2;
  96.     while (secondChild < len) {
  97.     if (*(first + secondChild) < *(first + (secondChild - 1)))
  98.         secondChild--;
  99.     *(first + holeIndex) = *(first + secondChild);
  100.     holeIndex = secondChild;
  101.     secondChild = 2 * (secondChild + 1);
  102.     }
  103.     if (secondChild == len) {
  104.     *(first + holeIndex) = *(first + (secondChild - 1));
  105.     holeIndex = secondChild - 1;
  106.     }
  107.     __push_heap(first, holeIndex, topIndex, value);
  108. }
  109.  
  110. template <class RandomAccessIterator, class T, class Distance>
  111. inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  112.                RandomAccessIterator result, T value, Distance*) {
  113.     *result = *first;
  114.     __adjust_heap(first, Distance(0), Distance(last - first), value);
  115. }
  116.  
  117. template <class RandomAccessIterator, class T>
  118. inline void __pop_heap_aux(RandomAccessIterator first,
  119.                RandomAccessIterator last, T*) {
  120.     __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
  121. }
  122.  
  123. template <class RandomAccessIterator>
  124. inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
  125.     __pop_heap_aux(first, last, value_type(first));
  126. }
  127.  
  128. template <class RandomAccessIterator, class Distance, class T, class Compare>
  129. void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
  130.            Distance len, T value, Compare comp) {
  131.     Distance topIndex = holeIndex;
  132.     Distance secondChild = 2 * holeIndex + 2;
  133.     while (secondChild < len) {
  134.     if (comp(*(first + secondChild), *(first + (secondChild - 1))))
  135.         secondChild--;
  136.     *(first + holeIndex) = *(first + secondChild);
  137.     holeIndex = secondChild;
  138.     secondChild = 2 * (secondChild + 1);
  139.     }
  140.     if (secondChild == len) {
  141.     *(first + holeIndex) = *(first + (secondChild - 1));
  142.     holeIndex = secondChild - 1;
  143.     }
  144.     __push_heap(first, holeIndex, topIndex, value, comp);
  145. }
  146.  
  147. template <class RandomAccessIterator, class T, class Compare, class Distance>
  148. inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  149.                RandomAccessIterator result, T value, Compare comp,
  150.                Distance*) {
  151.     *result = *first;
  152.     __adjust_heap(first, Distance(0), Distance(last - first), value, comp);
  153. }
  154.  
  155. template <class RandomAccessIterator, class T, class Compare>
  156. inline void __pop_heap_aux(RandomAccessIterator first,
  157.                RandomAccessIterator last, T*, Compare comp) {
  158.     __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
  159.            distance_type(first));
  160. }
  161.  
  162. template <class RandomAccessIterator, class Compare>
  163. inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  164.              Compare comp) {
  165.     __pop_heap_aux(first, last, value_type(first), comp);
  166. }
  167.  
  168. template <class RandomAccessIterator, class T, class Distance>
  169. void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
  170.          Distance*) {
  171.     if (last - first < 2) return;
  172.     Distance len = last - first;
  173.     Distance parent = (len - 2)/2;
  174.     
  175.     while (true) {
  176.     __adjust_heap(first, parent, len, T(*(first + parent)));
  177.     if (parent == 0) return;
  178.     parent--;
  179.     }
  180. }
  181.  
  182. template <class RandomAccessIterator>
  183. inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
  184.     __make_heap(first, last, value_type(first), distance_type(first));
  185. }
  186.  
  187. template <class RandomAccessIterator, class Compare, class T, class Distance>
  188. void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
  189.          Compare comp, T*, Distance*) {
  190.     if (last - first < 2) return;
  191.     Distance len = last - first;
  192.     Distance parent = (len - 2)/2;
  193.     
  194.     while (true) {
  195.     __adjust_heap(first, parent, len, T(*(first + parent)), comp);
  196.     if (parent == 0) return;
  197.     parent--;
  198.     }
  199. }
  200.  
  201. template <class RandomAccessIterator, class Compare>
  202. inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,
  203.               Compare comp) {
  204.     __make_heap(first, last, comp, value_type(first), distance_type(first));
  205. }
  206.  
  207. template <class RandomAccessIterator>
  208. void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  209.     while (last - first > 1) pop_heap(first, last--);
  210. }
  211.  
  212. template <class RandomAccessIterator, class Compare>
  213. void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
  214.            Compare comp) {
  215.     while (last - first > 1) pop_heap(first, last--, comp);
  216. }
  217.  
  218. __END_STL_NAMESPACE
  219.  
  220. #endif
  221.